The present invention generally relates to searching and more specifically to techniques for searching a data structure where entries in the data structure include information that guides a search.
A key is used to search a data structure for a certain value. When a key is large, searching for the key in the data structure may be inefficient and time consuming. Often, the key is hashed into a hash result using a hashing algorithm. The hash result is typically a smaller representation of the key and can be searched for in less time than the larger key.
Because keys are hashed into smaller hash results, multiple hash results may correspond to a single entry in the data structure. Thus, when an entry corresponding to the hash result is determined, the entry may not be the correct entry for the key. If the entry is not the correct entry for the key, a search for a different entry needs to be performed.
The entry that was determined may include multiple branches. Each branch may include an entry that is the correct entry for the key and each branch is searched for the hash result. Searching for the hash result in each branch includes many disadvantages. For example, the time to search each branch is very time consuming and inefficient. Thus, search times increase as data structures become more complicated and include more branches.